package com.hop.sort;

/**
 * 插入排序(直接插入排序、希尔排序)
 * @author Administrator
 *
 */
public class InsertSort {
	
	/**
	 * 直接插入排序
	 * 在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排
	 * 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
	 * 也是排好顺序的。如此反复循环，直到全部排好顺序
	 * @param array 待排序数组
	 */
	public void StraightSort(int array[]){
		long start = System.currentTimeMillis();
		for(int i = 1; i<array.length; i++){
			int j = i-1;
			int temp = array[i];
			for(;j>=0 && temp < array[j];j--){
				array[j+1] = array[j];  		//将大于temp的值整体后移一个单位
			}
			array[j+1] = temp;
		}
		long ent = System.currentTimeMillis();
		System.out.print("执行时间："+(start-ent)+"MS");
	}
	
	/**
	 * 希尔排序
	 * 基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，
	 * 每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，
	 * 在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
	 * @param a
	 */
	public void ShellSort(int a[]){
		double d1 = a.length;
		int temp = 0;
		long start = System.currentTimeMillis();
		while(true){
			d1 = Math.ceil(d1/2);
			int d = (int)d1;
			for(int x = 0;x<d;x++){
				for(int i = x+d;i<a.length;i+=d){
					int j = i-d;
					temp = a[i];
					for(;j>=0&&temp<a[j];j-=d){
						a[j+d] = a[j];
					}
					a[j+d] = temp;
				}
			}
			if(d==1){
				break;
			}
		}
		long ent = System.currentTimeMillis();
		System.out.print("执行时间："+(start-ent)+"MS");
	}
}
